/*
 * Copyright (c) 2018. J4dream created
 */

package com.j4dream.property.leetcode.basic;

import java.util.*;

public class TreeBasic {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    private long min = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        // 只满足子树条件。
//        if (root == null) return true;
//        if (root.left == null && root.right == null) return true;
//        if (root.left != null && root.left.val >= root.val) return false;
//        if (root.right != null && root.right.val <= root.val) return false;
//        return this.isValidBST(root.left) && this.isValidBST(root.right);

        //方法1： 如果是有效的，那么 二叉树 中序遍历出来的值就有序的。

        if (root == null) return true;
        if (isValidBST(root.left)) {
            if (root.val > min) {
                min = root.val;
                return isValidBST(root.right);
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode n1, TreeNode n2) {
        if (n1 == null && n2 == null) return true;
        if (n1 == null || n2 == null) return false;
        if (n1.val != n2.val) return false;
        return isSymmetric(n1.left, n2.right) && isSymmetric(n2.left, n1.right);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();

        if (root == null) return res;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        int size;
        TreeNode node;

        while (!queue.isEmpty()) {
            List<Integer> row = new ArrayList<>();
            size = queue.size();
            while (size-- > 0) {
                node = queue.poll();
                row.add(node.val);

                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(row);
        }

        return res;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        return buildBST(nums, 0, nums.length - 1);
    }

    private TreeNode buildBST(int[] nums, int start, int end) {
        if (start <= end) {
            int mid = (start + end) / 2;
            TreeNode node = new TreeNode(nums[mid]);
            node.left = buildBST(nums, start, mid - 1);
            node.right = buildBST(nums, mid + 1, end);
            return node;
        } else {
            return null;
        }
    }

}
